package 力扣.二分查找;

//数组被分成三个 非空 连续子数组，从左至右分别命名为 left ， mid ， right 。
//left 中元素和小于等于 mid 中元素和，mid 中元素和小于等于 right 中元素和。

public class 将数组分为三个字数组的方案数 {
    public static void main(String[] args) {
          int[] nums={1,2,2,2,5,0};
        int i = waysToSplit(nums);
        System.out.println(i);
    }
    //遇到区间问题，首先想到前缀和
    public static int waysToSplit(int[] nums) {
        final int m=1000000007;
        int n=nums.length;
        long num=0;
        //前缀和数组
        int[] sum = new int[n];
        sum[0]=nums[0];
        for (int i = 1; i < n; i++) {
            sum[i]=sum[i-1]+nums[i];
        }
        //第一刀的范围是[0,sum[n-1]/3]    第二刀的范围是[sum[left]*2,sum[left]+(sum[right]-sum[left])/2]
        for (int i = 0; i < n && sum[i] <= sum[n - 1] / 3; i++) {
              //找到第二刀位置的左边
            int left=minIndex(i+1,n-1,sum,sum[i]*2);
             //找到第二刀右边的位置
            int right=maxIndex(i+1,n-1,sum,sum[i]+(sum[n-1]-sum[i])/2);
            if (right>=left)
                num+=right-left+1;
        }
        return (int)(num%m);
    }

    //查找左侧边界
    private static int minIndex(int left, int right, int[] sum, int target) {
        //不写成(left+right)/2是为了避免超出int的范围
        while (left<=right){
            int mid=left+(right-left)/2;
            if (sum[mid]<target)
                left=mid+1;
            else if (sum[mid]>target)
                right=mid-1;
            else if (sum[mid]==target)
                right=mid-1;
        }
        return left;
    }
    //查找右侧边界
    public static int maxIndex(int left, int right, int[] nums, int target) {
        while (left<=right) {
            int mid = left + (right - left)/2;
            if (nums[mid]<target) {
                left = mid + 1;
            }
            else if (nums[mid]>target){
                right = mid-1;
            }
            else if(nums[mid]==target)
                left=mid+1;
        }
        return right;
    }
}
